# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        return str(self.val)


class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # 转成数组
        nodes = []
        if head is None:
            return None
        tmp = head
        while tmp:
            nodes.append(tmp)
            tmp = tmp.next

        start = 0
        end = len(nodes) - 1
        while start < end:

            if end == start + 1:
                nodes[start].next = nodes[end]
                nodes[end].next = None
            else:
                nodes[start].next = nodes[end]
                nodes[end].next = nodes[start + 1]
                if end == start + 2:
                    nodes[start + 1].next = None
            start = start + 1
            end = end - 1


def build(nodes):
    print(nodes)
    a = []
    for val in nodes:
        a.append(ListNode(val))

    for i in range(len(a) - 1):
        a[i].next = a[i + 1]
    return a[0]


if __name__ == '__main__':
    so = Solution()
    head = build([1, 2, 3, 4, 5, 6, 7, 8])
    so.reorderList(head)
    print(head)
